class Solution {
public:
/*
//暴力遍历
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() <= 0){
            return false;
        }
        for(int i = 0;i < matrix.size(); i++){
          for(int j = 0; j < matrix[0].size(); j++){
              if(matrix[i][j] == target){
                  return true;
              }
          }
        }
        return false;
    }
*/
    
//高效查找（一次排除一行或一列）
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix.size() <= 0 \
         || matrix[0].size() <= 0)   {
            return false;
        }

        int rows = matrix.size(), cols = matrix[0].size();
        int row = 0, col = cols - 1;
        
        while(row < rows && col >= 0){
            int index = matrix[row][col];
            if(index == target){
                return true;
            }
            else if(index < target){
                row++;
            }
            else{
                col--;
            }
        }

        return false;
    }
};